package com.zx._12_算法.数据结构.bitmap;

import java.lang.reflect.Field;
import java.util.Arrays;
import org.springframework.util.ReflectionUtils;

/**
 * @version v1.0
 * @Project: knowledge
 * @Title: SimpleBitMap
 * @Description: 简单实现一个bitMa
 *         SimpleBitMap2中实现的算法，已经很快，但是却面临一个新的问题，如果数据非常多，多达1个亿，每个整数是4个字节，那么一亿个整数数就是4亿个字节，
 *         1024字节是1kb，1024kb是1M,4亿个字节就381M的内存空间。如果没有这么多内存该怎么办？
 *         我们需要一种数据压缩的算法，用很少的空间来表示这一亿个数的存在与否。
 *         3. 位运算
 *         内存中的数据，最终的存储方式都是二进制，位运算就是对整数在内存中的二进制位进行操作。
 *
 *         3.1 按位与 &
 *         两个整数进行按位与运算，相同二进制位的数字如果都是1，则结果为1，有一个位为0，则结果为0， 下面是 3 & 7的计算过程
 *
 *         二进制    整数
 *
 *         0 1 1     3
 *         1 1 1     7
 *
 *         0 1 1     3
 *         3 & 7 = 3
 *
 *         3.2 按位或 |
 *         两个整数进行按位或运算，相同二进制位的数字如果有一个为1，则结果为1，都为0，则结果为0， 下面是 5 | 8 的计算过程
 *
 *         二进制        整数
 *
 *         0 1 0 1       5
 *         1 0 0 0       8
 *
 *         1 1 0 1       13
 *         5 | 8 = 13
 *
 *         3.3 左移 <<
 *         二进制向左移动 n 位，在后面添加 n 个0
 *         下面是 3<<1 计算过程。
 *
 *         二进制       整数
 *
 *         1 1      3
 *
 *         1 1 0      6
 *         3<<1 = 6
 *
 *         3.4 小试牛刀
 *         一组数，内容以为 3， 9， 19， 20，请用一个整数来表示这些四个数
 *
 *         var value = 0;
 *         value = value | 1<<3;
 *         value = value | 1<<9;
 *         value = value | 1<<19;
 *         value = value | 1<<20;
 *         console.log(value);
 *
 *         经过前面一系列的分析和位运算学习，现在，我们要重新设计一个类，实现addMember和isExist方法，用更快的速度，更少的内存。
 *         1. 数据范围是0到100，那么只需要4个整数就可以表示4*32个数的存在与否，创建一个大小为4的数组
 *         2. 执行addMember时，先用member/32，确定member在数组里的索引（arr_index），然后用member%32，确定在整数的哪个二进制位行操作(bit_index)，
 *         最后执行bit_arr[arr_index] = bit_arr[arr_index] | 1<<bit_index;
 *         3. 执行isExist时，先用member/32，确定member在数组里的索引（arr_index），然后用member%32，确定在整数的哪个二进制位行操作(bit_index)，
 *         最后执行bit_arr[arr_index] & 1<<bit_index，如果结果不为0，就说明memeber存在
 *
 *         缺点：压缩的比例还是小；扩展性不好，内部数组的大小在实例化的时候被限制了。
 * @author: zhangxue
 * @date: 2019年7月31日下午10:43:24
 * @company: 未知之地
 * @Copyright: Copyright (c) 2019
 */
public class BitmapImpl1 implements BitMap {

    // 压缩因子
    final int DIVISOR = 32;
    private int[] data = new int[10];

    public static void main(String[] args) throws Exception {
        int[] datas = {0, 3, 5, 6, 9, 34, 23, 78, 99};
        BitMap bitMap = new BitmapImpl1();
        for (int i = 0; i < datas.length; i++) {
            bitMap.addMember(datas[i]);
        }

        System.out.println(bitMap.isExist(3));  //true
        System.out.println(bitMap.isExist(7));  //false
        System.out.println(bitMap.isExist(78)); //true

        Field findField = ReflectionUtils.findField(BitmapImpl1.class, "data");
        findField.setAccessible(true);

        int[] data = (int[]) findField.get(bitMap);
        System.out.println(Arrays.toString(data));

    }

    @Override
    public void addMember(int member) {
        int arrIndex = member / DIVISOR;
        int bitIndex = member % DIVISOR;
        data[arrIndex] = data[arrIndex] | (1 << bitIndex);
    }

    /**
     * 时间复杂度= O(1)
     */
    @Override
    public boolean isExist(int member) {
        int arrIndex = member / DIVISOR;
        int bitIndex = member % DIVISOR;

        int bitIndexAfter = 1 << bitIndex;
        int bitValue = data[arrIndex];
        return (bitValue & bitIndexAfter) != 0;

    }
}
